package com.zbxx.search;

import java.util.*;

/**
 * 399 除法求值
 *
 * @author wanrj
 * @date 2023/6/1
 */
public class calcEquation {


    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        UnionFind find = new UnionFind(equations);
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            find.union(equation.get(0), equation.get(1), values[i]);
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            res[i] = -1d;
            List<String> query = queries.get(i);
            String l = query.get(0);
            String r = query.get(1);
            if (find.find(l) == null || find.find(r) == null) {
                continue;
            }
            if (!find.isConnected(l, r)) {
                continue;
            }
            if (l.equals(r)) {
                res[i] = 1d;
                continue;
            }
            HashSet<String> s = new HashSet<>();
            s.add(l);
            res[i] = find.dfs(l, r, s);
            res[i] = res[i] == 0 ? -1d : res[i];
        }
        return res;
    }

    public class UnionFind {
        Map<String, Map<String, Double>> values = new HashMap<>();

        Map<String, String> parent = new HashMap<>();

        public UnionFind(List<List<String>> equations) {
            equations.forEach(equation -> {
                values.putIfAbsent(equation.get(0), new HashMap<>());
                values.putIfAbsent(equation.get(1), new HashMap<>());
                parent.put(equation.get(0), equation.get(0));
                parent.put(equation.get(1), equation.get(1));
            });
        }

        public void union(String x, String y, double value) {
            String xr = find(x);
            String yr = find(y);
            values.get(x).put(y, value);
            values.get(y).put(x, 1d / value);
            if (xr.equals(yr)) {
                return;
            }
            parent.put(xr, yr);
        }

        public boolean isConnected(String x, String y) {
            return find(x).equals(find(y));
        }

        public String find(String x) {
            while (x != null && !x.equals(parent.get(x))) {
                parent.put(x, parent.get(parent.get(x)));
                x = parent.get(x);
            }
            return x;
        }

        public double dfs(String x, String y, Set<String> search) {
            Map<String, Double> side = values.get(x);
            if (side.isEmpty()) {
                return 0;
            }
            Double d = side.get(y);
            if (d != null) {
                return d;
            }
            for (String s : side.keySet()) {
                if (search.contains(s)) {
                    continue;
                }
                double res = 1;
                search.add(s);
                res *= side.get(s) * dfs(s, y, search);
                if (res != 0) {
                    return res;
                }
                search.remove(s);
            }
            return 0;
        }

    }


    public static void main(String[] args) {
        calcEquation c = new calcEquation();
        double[] res = c.calcEquation(Arrays.asList(
                        Arrays.asList("x1", "x2"),
                        Arrays.asList("x2", "x3"),
                        Arrays.asList("x3", "x4"),
                        Arrays.asList("x4", "x5")
                ),
                new double[]{
                        3.0,
                        4.0,
                        5.0,
                        6.0
                },
                Arrays.asList(
                        Arrays.asList("x1", "x5"),
                        Arrays.asList("x5", "x2"),
                        Arrays.asList("x2", "x4"),
                        Arrays.asList("x2", "x2"),
                        Arrays.asList("x2", "x9"),
                        Arrays.asList("x9", "x9")
                ));
        System.out.println(Arrays.toString(res));
    }

}
